package cn.topkinson.algorithm;

/**
 * @Author huangzihao
 * @Date 2021/2/12 19:31
 *
 * 很久很久以前，有一位国王拥有5座金矿，每座金矿的黄金储量不同，需要参与挖掘的工人人数也不同。
 * 例如有的金矿储量是500kg黄金，需要5个工人来挖掘；有的金矿储量是200kg黄金，需要3个工人 来挖掘…… 如果参与挖矿的工人的总数是10。
 * 每座金矿要么全挖，要么不挖，不能派出一半人挖取一半的金矿。
 * 要求用程序求出，要想得到尽可能多的黄金，应该选择挖取哪几座金矿？
 *
 */
public class GreedyGoldMine {
    public static void main(String[] args) {
        int[] values={6,3,5,4,6};
        int[] weights={2,2,6,5,4};
        int max=10;
        System.out.println("挖出的最大储量是："+maxValue(values,weights,max));

    }

    public static int maxValue(int[] values,int[]weights,int max){
        if(values==null|| values.length==0) return 0;
        if(weights==null|| weights.length==0) return 0;
        if(values.length!=weights.length|| max<=0) return 0;

        //初始化dp方程的二维数组，等待计算填充数据
        int[][] dpValue = new int[values.length+1][max+1];

        //int数组默认值为0，故不需显式设置初始化
        //二维数组遍历
        for (int i=1;i<=values.length;i++){  //从1遍历到结束
            for (int j = 1;j<=max;j++){      //背包从1到最大

                //当前的背包不足以新增物品，价值保持和上次一样
                if (j<weights[i-1]){
                    dpValue[i][j] = dpValue[i-1][j];
                }else{
                    //当前背包空间可以携带这一件新商品：
                    //不选：和上个选项一样：dpValue[i-1][j]
                    //选：本次新增的商品价值+上个选项去掉当前商品重量的情况下，的dp值：values[i]+dpValue[i-1][j-weights[i]]
                    //取两者最大
                    dpValue[i][j] = Math.max(
                            dpValue[i-1][j],
                            values[i-1]+dpValue[i-1][j-weights[i-1]]);
                }
            }
        }

        for (int i=0;i<values.length+1;i++){  //从1遍历到结束
            for (int j=0;j<max+1;j++){      //背包从1到最大
                System.out.print(dpValue[i][j]+",");
            }
            System.out.println();
        }

        //计算完毕后，取出最大位置的值，就是最大价值
        int maxValue = dpValue[values.length][max];
        int j=max;
        //遍历dp二维数组，找出放入背包的i,j
        for (int i = values.length;i>0;i--){
            //后一个比前一个数值大，表示这一次就选上了
            if (dpValue[i][j]>dpValue[i-1][j]){
                System.out.println("选择：序号为"+(i-1)+"的金矿价值：["+values[i-1]+"]-消耗工人：["+weights[i-1]+"]");
                j = j-weights[i-1];
            }
        }
        return maxValue;

    }

}
